# 砍柴(好题)
from leetcode import test_function as tf
import math
import bisect


def sieve(num: int):
    """
    埃拉托斯特尼筛法：求出小于等于 n 的所有质数
    具体方法为:
    求出sqrt(n) + 1为循环的上限, 因为假设一个合数 m <= n 那么m一定可以分解为两个因数a和b, 即:a * b = m
    假设 a <= b, 那么a <= sqrt(m) <= sqrt(n).
    因此当筛到a时，m已经被标记为合数了。因此，不需要检查超过√n的数，因为它们的最小质因数已经被处理过了。
    原始状态:
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    F T T T T T T T T  T  T  T  T  T  T  T  T  T  T  T
    i = 2时: 2为素数, 将2的倍数全部标记为合数(非素数)
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    F T T F T F T F T  F  T  F  T  F  T  F  T  F  T  F
    i = 3时: 3为素数, 将3的倍数全部标记为合数
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    F T T F T F T F F  F  T  F  T  F  F  F  T  F  T  F
    i = 4时: 4已经被标记为合数, 不处理
    i = 5时: 5为素数, 将5的倍数全部标记为合数
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    F T T F T F T F F  F  T  F  T  F  F  F  T  F  T  F
    """
    is_prime = [True] * (num + 1)
    is_prime[0] = is_prime[1] = False  # 0 和 1 不是质数
    # 从 2 到 sqrt(n) 进行筛选
    for i in range(2, int(math.sqrt(num)) + 1):
        if is_prime[i]:
            # 将 i 的倍数标记为非质数
            for j in range(i * i, num + 1, i):
                is_prime[j] = False
    # 返回所有质数的列表
    return [i for i, prime in enumerate(is_prime) if prime]


def get_primes_bf(num: int):
    # 求出小于等于 n 的所有质数
    res = []
    for i in range(2, num):
        flag = False
        for j in range(2, int(i ** 0.5) + 1):
            if i % j == 0:
                flag = True
                break
        if not flag:
            res.append(i)
    return res


def determine_winners(arr):
    if not arr:
        return []
    max_n = max(arr)
    primes = sieve(max_n) if max_n >= 2 else []

    """
    创建动态规划表, 动态规划求解状态：
    dp[x] 表示当前木头长度为 x 时（轮到当前玩家）是否存在必胜策略。
    递推公式：dp[x] = True 如果存在质数 p (2<=p<=x) 使得 dp[x-p] 为 False
    """
    dp = [False] * (max_n + 1)
    # 定义：当 x=0 或 x=1 时，当前玩家没有合法走法，必败
    dp[0] = dp[1] = False
    # 从 2 开始计算每个状态
    for x in range(2, max_n + 1):
        idx = bisect.bisect_right(primes, x)  # 定位最大的质数p_max
        valid_primes = primes[:idx]  # 将所有小于p_max的质数截取出来
        valid_primes_reversed = valid_primes[::-1]  # 逆序，优先检查大的质数
        can_win = False
        for p in valid_primes_reversed:  # 遍历所有可能的质数
            prev = x - p
            if prev >= 0 and not dp[prev]:  # 如果选择 p 后，对手状态为必败，则当前状态为必胜
                can_win = True
                break  # 存在一个必胜走法即可退出内层循环
        dp[x] = can_win
    results = []

    # 直接通过查dp表来获得答案
    for n in arr:
        if n <= 1:
            results.append(0)
        else:
            results.append(1 if dp[n] else 0)
    return results


arr = []
res = []
with open("../../data/2024_e.in", "r") as file:
    n = int(file.readline())
    for i in range(n):
        arr.append(int(file.readline()))
with open("../../data/2024_e.out", "r") as file:
    for i in range(n):
        res.append(int(file.readline()))

inp = {"arr": arr}
out = res

tf(determine_winners, inp, out)
# tf(get_primes_bf, {"num": a}, res)
# n = int(input())
# inp = []
# for i in range(n):
#     inp.append(int(input()))
